CS211 DATA STRUCTURES AND ALGORITHMS II

2ND SCIENCE & HIGHER DIPLOMA IN INFORMATION TECHNOLOGY

LABORATORY EXAM 2

SAMPLE QUESTIONS

 

 

  1. The following is a template for a TreeNode class for Huffman Coding. Modify the constructor TreeNode( ) to initialise the weight object of the TreeNode class:

 

public class TreeNode {

private Object item;

private Object weight;

private TreeNode leftChild;

private TreeNode rightChild;

 

public TreeNode(Object newItem) {

// Initializes tree node with item and no children.

item = newItem;

leftChild = null; // reference has no object

rightChild = null;

} // end constructor

 

 

 

 

  1. Modify the following constructor for the class BinaryTreeBasis to include a weight object passed to the constructor for class TreeNode:

 

public BinaryTreeBasis(Object rootItem) {

root = new TreeNode(rootItem, null, null);

} // end constructor

 

 

 

 

  1. Complete the following code segment for inserting a new node in a Binary Tree as used in constructing a Huffman optimal code tree. Include comments with the code.

 

protected TreeNode insertItem(TreeNode tNode, KeyedItem newItem,

Float weight) {

if (tNode == null) {

// comments

//

 

 

 

} // end if

 

 

 

  1. Give pseudo code for Huffman's algorithm to construct an optimal code tree. Assume the data structure used to store the symbols and probabiliities is an array of Tree objects. 

    2.  

     

  2. Using diagrams, show the construction of an optimal code tree from the following symbols and associated probabilities.

    3. SYMBOL

    E

    O

    I

    T

    B

    A

    PROBABILITY

    0.074

    0.092

    0.08

    0.120

    0.101

    0.071

     

     

     

  3. Complete the following code template for the class PATH for the methods AddTpPath() and RemoveFromPath().

    4.  

    public class Path {

    final static int MAXPATHLENGTH = 20;

    int PathComponents[] = new int[MAXPATHLENGTH];

    int PathLength;

     

    public void Path() {

    for(int i=0;i<MAXPATHLENGTH;i++)

    PathComponents[i] =0;

    PathLength=0;

    }

     

    public void AddToPath(int direction) {

    if(PathLength < MAXPATHLENGTH)

    {

     

     

    }

    else

    System.out.println("Error maximum pathlength reached\n");

    }

     

    public void RemoveFromPath() {

    if (PathLength > 0)

     

     

    }

     

    public void PrintPath() {

    for(int i=0;i<PathLength;i++)

    System.out.print(PathComponents[i]);

    System.out.println();

    }

    }

     

  4. Comment the following Java code for the method LeafNodeHelper( ) which computes the code for each symbol in an optimal code tree and prints the symbols with their codes. Write your comments in the space provided indicated by the word comments.

 

public void LeafNodeHelper(TreeNode tNode, Path code) {

if(tNode != null)

{

// comments

//

//

if((tNode.getLeft()==null) && (tNode.getRight()==null))

{

//comments

//

KeyedItem nodeItem = (KeyedItem)tNode.getItem();

//

//

//

System.out.print(nodeItem.getKey());

code.PrintPath();

}

else

{

// comments

//

//

//

code.AddToPath(0);

LeafNodeHelper(tNode.getLeft(),code);

code.RemoveFromPath();

// comments

//

//

//

code.AddToPath(1);

LeafNodeHelper(tNode.getRight(),code);

code.RemoveFromPath();

}

}

}